/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：BinaryHeap.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-04
Function List ：
Description   ：Binary Heap
******************************************************/

#include "BinaryHeap.h"
#include <stdlib.h>   // for malloc
#include <limits.h>   // for INT_MAX
#include "FatalError.h"

#define MinPQSize   (10)
#define MinData     (-32767)

struct HeapStruct {
    int Capacity;
    int Size;
    ElementType *Elements;
};

// Static Function Lists
static int GetParentIndex(int Index);
static int GetChildIndex(int Index);
static void Swap(ElementType *Lhs, ElementType *Rhs);
static void PercolateUp(int Child, PriorityQueue H);
static void PercolateDown(int Parent, PriorityQueue H);

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    if (MaxElements < MinPQSize) {
        Error("Priority queue size is too small");
    }

    /* Allocate priority queue */
    H = (PriorityQueue)malloc(sizeof(struct HeapStruct));
    if (H == NULL) {
        FatalError("Out of space!!!");
    }

    /* Allocate the array plus one extra for sentinel */
    H->Elements = (ElementType *)malloc((MaxElements + 1) * sizeof(ElementType));
    if (H->Elements == NULL) {
        FatalError("Out of space!!!");
    }

    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;

    return H;
}

void Destroy(PriorityQueue H) {
    free(H->Elements);
    free(H);
}

void MakeEmpty(PriorityQueue H) {
    H->Size = 0;
}

/**    Binary Heap
 *          1
 *        /   \
 *       2     3
 *      / \   / \
 *     4   5 6   7
 *
 * Child  = Parent * 2;
 * Parent = Child / 2;
 */
static int GetParentIndex(int Index) {
    return Index / 2;
}

static int GetChildIndex(int Index) {
    return Index * 2;
}

static void Swap(ElementType *Lhs, ElementType *Rhs) {
    ElementType Tmp;

    Tmp = *Lhs;
    *Lhs = *Rhs;
    *Rhs = Tmp;
}

static void PercolateUp(int Child, PriorityQueue H) {
    int Parent;

    while (Child != 0) {
        Parent = GetParentIndex(Child);
        if (H->Elements[Parent] > H->Elements[Child]) {
            /* Swap */
            Swap(&H->Elements[Parent], &H->Elements[Child]);
            Child = Parent;
        } else {
            break;
        }
    }
}

static void PercolateDown(int Parent, PriorityQueue H) {
    int Child;

    Child = GetChildIndex(Parent);
    while (Child <= H->Size) {
        /* Find smaller child */
        if (Child != H->Size &&
            H->Elements[Child + 1] < H->Elements[Child]) {
            Child = Child + 1;
        }

        /* Percolate one level */
        if (H->Elements[Child] < H->Elements[Parent]) {
            /* Swap */
            Swap(&H->Elements[Child], &H->Elements[Parent]);

            /* Update index */
            Parent = Child;
            Child = GetChildIndex(Parent);
        } else {
            break;
        }
    }
}

/* H->Element[0] is a sentinel */
void Insert(ElementType X, PriorityQueue H) {
    int i;

    if (IsFull(H)) {
        Error("Priority queue is full");
        return;
    }

    /* Percolate up */
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2) {
        H->Elements[i] = H->Elements[i / 2];
    }

    H->Elements[i] = X;
}

ElementType DeleteMin(PriorityQueue H) {
    int i;
    int Child;
    ElementType MinElement;
    ElementType LastElement;

    if (IsEmpty(H)) {
        Error("Priority queue is empty");
        return H->Elements[0];
    }

    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    /* Percolate down */
    for (i = 1; i * 2 <= H->Size; i = Child) {
        /* Find smaller child */
        Child = i * 2;
        if (Child != H->Size && 
            H->Elements[Child + 1] < H->Elements[Child]) {
            ++Child;
        }

        /* Percolate one level */
        if (LastElement > H->Elements[Child]) {
            H->Elements[i] = H->Elements[Child];
        } else {
            break;
        }
    }

    H->Elements[i] = LastElement;

    return MinElement;
}

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H)) {
        return H->Elements[1];
    } else {
        Error("Priority Queue is empty");
        return H->Elements[0];
    }
}

/* Put N keys into binary heap */
PriorityQueue BuildHeap(ElementType A[], int N) {
    PriorityQueue H;
    int i;

    H = Initialize(N * 2);
    H->Size = N;
    for (i = 0; i < N; ++i) {
        H->Elements[i + 1] = A[i];
    }

    for (i = N / 2; i > 0; --i) {
        PercolateDown(i, H);
    }

    return H;
}

void DecreaseKey(int P, ElementType X, PriorityQueue H) {
    if (P <= 0 || P > H->Size) {
        Error("Position out of range");
    }

    H->Elements[P] = H->Elements[P] - X;
    PercolateUp(P, H);
}

void IncreaseKey(int P, ElementType X, PriorityQueue H) {
    if (P <= 0 || P > H->Size) {
        Error("Position out of range");
    }

    H->Elements[P] = H->Elements[P] + X;
    PercolateDown(P, H);
}

void Delete(int P, PriorityQueue H) {
    if (P <= 0 || P > H->Size) {
        Error("Position out of range");
    }

    DecreaseKey(P, INT_MAX, H);
    DeleteMin(H);
}

int IsEmpty(PriorityQueue H) {
    return H->Size == 0;
}

int IsFull(PriorityQueue H) {
    return H->Size == H->Capacity;
}

int Size(PriorityQueue H) {
    return H->Size;
}

ElementType Retrieve(PriorityQueue H, int Index) {
    return H->Elements[Index];
}

// EOF

